package com.LeeCode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 第 K 大的完美二叉子树的大小
 */

public class Code3319 {
    public static void main(String[] args) {
        Integer[] arr = {5, 3, 6, 5, 2, 5, 7, 1, 8, null, null, 6, 8};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code3319().kthLargestPerfectSubtree(root, 2));
    }

    public int kthLargestPerfectSubtree(TreeNode root, int k) {
        List<Integer> hs = new ArrayList<>();
        dfs(root, hs);

        if (k > hs.size()) {
            return -1;
        }
        Collections.sort(hs);
        return (1 << hs.get(hs.size() - k)) - 1;
    }

    private int dfs(TreeNode node, List<Integer> hs) {
        if (node == null) {
            return 0;
        }
        int leftH = dfs(node.left, hs);
        int rightH = dfs(node.right, hs);
        if (leftH < 0 || leftH != rightH) {
            return -1; // 不合法
        }
        hs.add(leftH + 1);
        return leftH + 1;
    }
}
